class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        result = []
        row_begin, col_begin = 0, 0
        row_end, col_end = len(matrix)-1, len(matrix[0])-1
        direction = "right"
        while row_begin <= row_end and col_begin <= col_end:
            if direction == "right":
                for col in range(col_begin, col_end+1):
                    result.append(matrix[row_begin][col])
                row_begin += 1
                direction = "down"
            elif direction == "down":
                for row in range(row_begin, row_end+1):
                    result.append(matrix[row][col_end])
                col_end -= 1
                direction = "left"
            elif direction == "left":
                for col in range(col_end, col_begin-1, -1):
                    result.append(matrix[row_end][col])
                row_end -= 1
                direction = "up"
            elif direction == "up":
                for row in range(row_end, row_begin-1, -1):
                    result.append(matrix[row][col_begin])
                col_begin += 1
                direction = "right"
        return result
